import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-07-19
 * Time: 22:54
 */

public class SmallestInfiniteSet {
    // 记录连续数字的起始位置
    private int time = 1;
    // 记录添加进去的不连续的数字
    private PriorityQueue<Integer> minHeap;
    private Set<Integer> set;


    public SmallestInfiniteSet() {
        this.minHeap = new PriorityQueue<>();
        this.set = new HashSet<>();
    }

    public int popSmallest() {
        if (minHeap.isEmpty()) {
            return time++;
        }
        int peek = minHeap.peek();
        if (peek < time) {
            set.remove(peek);
            return minHeap.poll();
        }
        return time++;
    }

    public void addBack(int num) {
        if (num >= time) {
            // 还没删除过呢, 不用添加
            return;
        }
        if (!set.contains(num)) {
            set.add(num);
            minHeap.offer(num);
        }
    }
}
